package cn.lr.demo;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;


public class Solution {
	public static void main(String[] args) {
		Solution s = new Solution();
		s.isAnagram("a","b");
	}
	//判断两个字符串的  包含的字符 是否一样
	public boolean isAnagram(String s, String t){
		boolean flag = true;
		if(null!=s&&t!=null){
			int len1 = s.length();
			int len2 = t.length();
			if(len1==len2){
				char[] c1 = s.toCharArray();
				char[] c2 = t.toCharArray();
				Arrays.sort(c1);
				Arrays.sort(c2);
				s = new String(c1);
				t = new String(c2);
				if(s.equals(t)){
					flag = true;
				}else{
					flag = false;
				}
			}else{
				flag = false;
			}
		}else if((null==s&&null!=t)||(null!=s&&null==t)){
			flag = false;
		}else{
			flag = true;
		}
		return flag;
	}
	//判断两个字符串的  包含的字符 是否一样  超时。。。。。。等待解决
	public boolean isAnagram1(String s, String t) {
		boolean flag = true;
		if(null!=s&&t!=null){
			if(s.length()==t.length()){
				char[] c1 = s.toCharArray();
				boolean flag1 = true;
				for(char c:c1){
					StringBuffer sb = new StringBuffer();
					sb.append(c);
					String st = sb.toString();
					System.err.println(st);
					if(!t.contains(st)){
						flag1 = false;
					}else{
						String t1 = t.replaceFirst(st, "");
						t = t1;
					}
				}
				flag = flag1;
			}else{
				flag = false;
			}
			
		}else if((null==s&&null!=t)||(null!=s&&null==t)){
			flag = false;
		}else{
			flag = true;
		}
		return flag;
    }
	//判断两个树  是否是相同的
	public boolean isSameTree(TreeNode p, TreeNode q){
		boolean flag = true;
		if(null!=p&&q!=null){
			if(p.val==q.val){
				boolean flag1 = isSameTree(p.left, q.left);
				boolean flag2 = isSameTree(p.right, q.right);
				flag = flag1&flag2;
			}else{
				flag = false;
			}
		}else if((null==p&&null!=q)||(null!=p&&null==q)){
			flag = false;
		}else{
			flag = true;
		}
		
		return   flag;
	}
	//删除 linkList　节点
	public void deleteNode(ListNode node){
		if(null!=node){
			ListNode next = node.next;
			node.val = next.val;
			node.next = next.next;
		}
	}
	//翻转二叉树  递归
	public TreeNode invertTree(TreeNode root){
		if(root==null){
			return null;
		}
		TreeNode temp = root.getLeft();
		root.left = root.getRight();
		root.right = temp;
		invertTree(root.left);
		invertTree(root.right);
		return root;
	}
	//利用队列实现     后续在研究
	public TreeNode invertTree2(TreeNode root) {
	    if (root == null) return null;
	    Queue<TreeNode> queue = new LinkedList<TreeNode>();
	    queue.add(root);
	    while (!queue.isEmpty()) {
	        TreeNode current = queue.poll();
	        TreeNode temp = current.left;
	        current.left = current.right;
	        current.right = temp;
	        if (current.left != null) queue.add(current.left);
	        if (current.right != null) queue.add(current.right);
	    }
	    return root;
	}
	//计算  二叉树的深度  递归
	public int maxDepth(TreeNode root){
		if(null!=root){
			int i = 0;
			int j = 0;
			TreeNode l = root.left;
			TreeNode r = root.right;
			i = maxDepth(l);
			j = maxDepth(r);
			return i>j?i+1:j+1; 
		}else{
			return 0;
		}
	}
	//翻转字符串  字符串转换成char 数组
	public String reverseString(String s) {
		char[] strings = s.toCharArray();
		StringBuffer str = new StringBuffer();
		for(int i=strings.length-1;i>=0;i--){
			if(strings[i] != '\n'){
				str.append(strings[i]);
			}
		}
		return str.toString();
    }
	//求 数字 各位的和  知道  和为小于10的为止 while 循环
	public int addDigits(int num) {
        String str = String.valueOf(num);
        int a =num;
        while(str.length()>1){
        	a=0;
        	char[] strings = str.toCharArray();
        	for(int i=0;i<strings.length;i++){
        		String s = ""+strings[i];
        		a = a+Integer.valueOf(s);
        	}
        	str = String.valueOf(a);
        }
        
        return a;
    }
	//英语不好   第一次没读懂题目 看了答案才明白题目的意思不   
    //题目意思是   有一堆石头  每次扔掉1-3个石头   只有扔掉最后一个人胜利  
    //根据这个可以 判断  只有当石头的总个数为4或4的倍数时不管你第一次扔几个  最后输的人都是你
	//所以想要赢   石头的数目必须 保证  
    public boolean canWinNim(int n) {
        return n%4!=0;
    }
    //获取两个数的和
    public int getSum(int a, int b) {
        int c = a+b;
        return c;
    }
    //把数组中的0 移动到到数组最后
    public void moveZeroes(int[] nums) {
        for(int i=nums.length-1;i>=0;i--){
			 int a = nums[i];
			 if(i<nums.length-1){
				 if(a==0){
					 for(int j=nums.length-1;j>=i;j--){
						 if(nums[j]!=0){
							 int tem = nums[i];
							 nums[i] = nums[j];
							 nums[j] = tem;
							 continue;
						 }
					 }
				 }
			 }
		 }
    }
    //求两个数组的交集
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<String> set = new HashSet<String>();
		 for(int i=0,len=nums1.length;i<len;i++){
			 for(int j=0,len2=nums2.length;j<len2;j++){
				 if(nums1[i]==nums2[j]){
					 set.add(""+nums1[i]);
				 }
			 }
		 }
		 Object[] array = set.toArray();
		 int[] ar = new int[array.length];
		 for(int z=0;z<array.length;z++){
			 ar[z] =  Integer.valueOf((String)array[z]);
		 }
		 return ar;
    }
    
    /**
	 * Given an array of size n, 
	 * find the majority element. The majority element is the element that appears more than [ n/2 ] times.
	 * You may assume that the array is non-empty and the majority element always exist in the array
	 */
	public int majorityElement(int[] nums) {
		int len = nums.length;
		int mid = len/2;
		int temp;
		insertSort(nums);
		//selectSort(nums);
		//quickSort(nums, 0, len-1);
		for(int a:nums){
			System.err.println(a);
		}
		return nums[mid];
    }
	//快速排序 超时
	public void quickSort(int[] nums,int left,int right){
		if(left<right){
			 int key = nums[left];
             int low = left;
             int high = right;
             while(low < high){
                 while(low < high && nums[high] >= key){
                         high--;
                 }
                 nums[low] = nums[high];
                 while(low < high && nums[low] <= key){
                         low++;
                 }
                 nums[high] = nums[low];
             }
             nums[low] = key;
             quickSort(nums,left,low-1);
             quickSort(nums,low+1,right);
		}
	}
	//选择排序  超时
	public  void selectSort(int[] numbers) {   
	    int size = numbers.length, temp;   
	    for (int i = 0; i < size; i++) {   
	        int k = i;   
	        for (int j = size - 1; j >i; j--)  {   
	            if (numbers[j] < numbers[k])  k = j;   
	        }   
	        temp = numbers[i];   
	        numbers[i] = numbers[k];   
	        numbers[k] = temp;   
	    }   
	}  
	//插入排序
	public  void insertSort(int[] numbers) {   
	    int size = numbers.length, temp, j;   
	    for(int i=1; i<size; i++) {   
	        temp = numbers[i];   
	        for(j = i; j > 0 && temp < numbers[j-1]; j--)   
	            numbers[j] = numbers[j-1];   
	        numbers[j] = temp;   
	    }
	}  

}
